/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/9
 * \* Time: 18:06
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 二叉搜索树的后序遍历序列 {
    public boolean verifyPostorder(int[] postorder){
        return recur(postorder,0,postorder.length-1);
    }
    boolean recur(int[] postorder, int i, int j){
        //此时节点只有一个直接返回true
        if(i>=j-1){
            return true;
        }
        int p=i;
        //找到第一个右子树节点
        while (postorder[p]<postorder[j]){
            p++;
        }
        int m=p;
        //找到第一个比右子树晓得节点并在后面判断该节点就是根节点
        while (postorder[p]>postorder[j]){
            p++;
        }
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
}